1201. Ugly Number III.go

package leetcode

funcnthUglyNumber(nint, aint, bint, cint) int {
low, high:=int64(0), int64(2*1e9)
forlow<high {
mid:=low+ (high-low)>>1
ifcalNthCount(mid, int64(a), int64(b), int64(c)) <int64(n) {
low=mid+1
 } else {
high=mid
 }
 }
returnint(low)
}

funccalNthCount(num, a, b, cint64) int64 {
ab, bc, ac:=a*b/gcd(a, b), b*c/gcd(b, c), a*c/gcd(a, c)
abc:=a*bc/gcd(a, bc)
returnnum/a+num/b+num/c-num/ab-num/bc-num/ac+num/abc
}

funcgcd(a, bint64) int64 {
forb!=0 {
a, b=b, a%b
 }
returna
}